#include <iostream>
using namespace std;

int numDecodings(string s);
int numDecodings2(string s);
int CountSub(string &s, int index);

int main(){
    cout<<numDecodings2("301")<<endl;
    return 0;
}

int numDecodings(string s) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    if(s.size() == 0){
        return 0;
    }
    return CountSub(s,0);
} 

int CountSub(string &s, int index){
    int res = 0;
    while(index < s.size()){
        int first = s[index] - '0';
        if(first == 0){
            return 0;
        }
        if(first > 2){
            ++index;
        }
        else{
            if(index+1 == s.size()){
                return 1;
            }
            int second = s[index+1] - '0';
            if(second == 0){
                index += 2;
            }
            else if(first*10+second > 26){
                ++index;
            }
            else{
                res += CountSub(s, index+1);
                res += CountSub(s, index+2);
                return res;
            }
        }
    }
    return 1;
}

int numDecodings2(string s) {    
    int length = s.size();
    if(length == 0)
        return 0;
    if(s[0] == '0'){
        return 0;
    }
    if(length == 1){
        return 1;
    }
    int *ways = new int[length];
    ways[0] = 1;
    ways[1] = 0;
    if(s[1] != '0')
        ways[1] += 1;
    int firstsum = (s[0]-'0')*10+(s[1]-'0');
    if(firstsum<27 && firstsum>9)
        ways[1] += 1;

    for(int index = 2; index<length; ++index){
        ways[index] = 0;
        // parse last one
        if(s[index] != '0')
            ways[index] += ways[index-1];
        // parse last two
        int sum = (s[index-1]-'0')*10+(s[index]-'0');
        if(sum<27 && sum>9)
            ways[index] += ways[index-2];
    }
    int res = ways[length - 1];
    delete []ways;
    return res;
}